(Problem) 002 Even Fibonacci numbers

작성일 In 댓글:

Project Euler

  • 공식 홈페이지 - projecteuler.net
  • 한글 번역 - projecteuler @kr
  • (HackerRank) ProjectEuler+ - hackerrank.com

Problem

Even Fibonacci numbers


problem <번역>

solution

Simple Code

문제에 충실하게 4백만(4,000,000) 보다 작은 피보나치 수열에서 짝수들의 합을 구했다
(짧게 코드를 구현할 수 있지만 가독성을 위해 피보나치 수열을 만들고 짝수들의 합을 구하는 함수를 따로 정의했다)

002_Even_Fibonacci_numbers.py
def fibonacci(max_num):
    numbers = [1, 2]

    while numbers[-1] < max_num:
        numbers.append(numbers[-2] + numbers[-1])

    return numbers[:-1]


def sum_of_the_even_valued(numbers):
    total = 0
    for n in numbers:
        if n % 2 == 0:
            total += n

    return total

print(sum_of_the_even_valued(fibonacci(4000000)))
HackerRank

위 풀이 방식을 그대로 적용해도 문제 없이 모든 테스트 케이스를 통과한다.

002_for_HacerRank.py
def fibonacci(max_num):
    numbers = [1, 2]

    while numbers[-1] < max_num:
        numbers.append(numbers[-2] + numbers[-1])

    return numbers[:-1]


def sum_of_the_even_valued(numbers):
    total = 0
    for n in numbers:
        if n % 2 == 0:
            total += n

    return total


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        N = int(input())
        print(fibonacci(N))
        print(sum_of_the_even_valued(fibonacci(N)))

하지만 짝수인 피보나치 수열들을 잘 살펴보면 [2, 8, 34, 144, 610, …]
8 = 2 * 4 + 0
34 = 8 * 4 + 2
144 = 34 * 4 + 8
610 = 144 * 4 + 34
즉,
다음 짝수 = 이전 짝수 * 4 + 전전 짝수
라는 규칙을 발견할 수 있다

002_even_fibonnacci.py
def even_fibonacci(max_num):
    prev, cur, total = 0, 2, 0

    while cur <= max_num:
        total += cur

        prev, cur = cur, cur * 4 + prev

    return total


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        N = int(input())
        print(even_fibonacci(N))

피보나치 수열에서 짝수들은 3칸씩 떨어져 있음을 알게되었다.
불필요하게 모든 피보나치 수열을 구하지 말자